package com.fang.algorithm.zuo.dp;

/**
 * @author lingxiao.fang
 * @Desc N皇后问题
 * 一个N*N的棋盘摆放皇后，求摆放多少种方法
 * 要求任何一个皇后不同行、不同列、也不能在一条斜线上
 * @createTime 2025/3/16 17:05
 */
public class Test02_NEmpress {

    public static void main(String[] args) {
        int n = 8;
        int[] record = new int[n];
        int result = nEmpress(n, 0, record);
        System.out.println(result);
    }

    /**
     * @param n
     * @param index 当前行
     * @param record 记录列皇后的位置index+record[index]形成xy坐标
     */
    private static int nEmpress(int n, int index, int[] record) {
        if (index == n) {
            return 1;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 校验当前index的皇后是否满足放置的要求
            if (currValid(record, index, i)) {
                record[index] = i;
                ans += nEmpress(n, index + 1, record);
            }
        }
        return ans;
    }

    /**
     * 校验当前index的皇后是否满足放置的要求
     * @param record 皇后位置数据
     * @param index 行
     * @param curr 列
     * @return
     */
    private static boolean currValid(int[] record, int index, int curr) {
        for (int k = 0; k < index; k++) {
            // 已经放置的皇后
            if (curr == record[k] || Math.abs(record[k] - curr) == Math.abs(index - k)) {
                return false;
            }
        }
        return true;
    }
}
